package BinaryTree;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * @author Liaorun
 */
public class TreeMaxWidth {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    public static int w(Node head) {
        if (head == null) {
            return 0;
        }

        LinkedList<Node> queue = new LinkedList<>();

        // 先把头节点放到队列
        queue.add(head);

        // 记录节点在那一层的map
        HashMap<Node, Integer> levelMap = new HashMap<>();

        // 当前在那一层，默认为1
        int curLevel = 1;

        // 当前层有多少节点，默认0个
        int curLevelNodes = 0;

        // 节点最多的层有多少节点
        int max = Integer.MIN_VALUE;

        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            // 获得当前节点所在的层数
            Integer curNodeLevel = levelMap.get(cur);

            if (curNodeLevel == curLevel) {
                // 还在老的一层
                curLevelNodes++;
            } else {
                // 来到新的一层
                // 判断是否更新节点最多的数
                max = Math.max(max, curLevelNodes);
                // 层数 + 1
                curLevel++;
                // 节点数记录重置
                curLevelNodes = 1;
            }
            System.out.println(cur.value);

            // 如果左孩子不为空，放到队列
            if (cur.left != null) {
                // 记录节点所在的层数
                levelMap.put(cur.left, curNodeLevel + 1);
                queue.add(cur.left);
            }

            // 如果右孩子不为空，放到队列
            if (cur.right != null) {
                // 记录节点所在的层数，为当前节点所在层数 + 1
                levelMap.put(cur.right, curNodeLevel + 1);
                queue.add(cur.right);
            }
        }

        // 因为最后一层没有下一层所以50行的代码进不去
        // 如果最后一层的节点最多，max的值就更新不了了
        return Math.max(max, curLevelNodes);

    }


    public static int getMaxWidth(Node head) {
        if (head == null) {
            return 0;
        }
        int maxWidth = 0;
        int curWidth = 0;
        // 目前的层数
        int curLevel = 0;
        // node 所在的层数
        HashMap<Node, Integer> levelMap = new HashMap<>();

        levelMap.put(head, 1);

        return 0;
    }
}
